﻿public class Solution {
    public int MaxProfit(int k, int[] prices)
    {
        // 不操作，第一次持有，第一次不持有……
        int[,] dp = new int[prices.Length, 2*k + 1];
        dp[0, 0] = 0;
        // 初始化
        for (int i = 1; i <= 2*k; i++)
        {
            if (i % 2 != 0) dp[0, i] = -prices[0];
            else dp[0, i] = 0;
        }
        
        // 递推公式
        for (int i = 1; i < prices.Length; i++)
        {
            for (int j = 1; j <= 2*k; j++)
            {
                // 持有
                if (j % 2 != 0)
                {
                    dp[i, j] = Math.Max(dp[i - 1, j], dp[i - 1, j - 1] - prices[i]);
                }
                else // 不持有
                {
                    dp[i, j] = Math.Max(dp[i - 1, j], dp[i - 1, j - 1] + prices[i]);
                }
            }
        }

        return dp[prices.Length - 1, 2*k];
    }

    public static void Main(string[] args)
    {
        int k = 2;
        int[] prices = [3, 2, 6, 5, 0, 3];

        Solution solution = new Solution();
        int res = solution.MaxProfit(k, prices);
        Console.WriteLine(res);
    }
}